Instructions:¶

  1. Read section 8.6 of your text and contemplate problem 10 (it's a pain, so you don't have to go through it all, just think about what the process would entail). You can do it for extra credit.

  2. Take or find an image, and using the tools in this Python notebook, find the rank k approximation of the matrix of your image for a few different values of k. I will look through the code below for your work.

  3. Assume that the amount of memory taken by a matrix is the number of entries of the matrix. When the computer saves the original image, it saves the whole original image matrix $A$, but when it saves the SVD it saves the matrices $U$ and $V$ and the list of singular values along the diagonal of $\Sigma$. Compare the size of your original image file, the size of the full singular value decomposition, and the size of the approximations you found in part 2. How much space did you save? Find a value of k that’s a good balance between file size and image quality. Enter your answer to this question in the indicated cell below.

  4. The rank k approximation uses the first k columns of the matrix $U$, the first k rows of the matrix $V$, and the first k singular values along the diagonal of the matrix $\Sigma$. Try approximating by taking a different set of rows and columns, for example, skipping the first 3 columns of $U$, rows of $V$, and diagonal values of $\Sigma$. How much worse does the image quality get? This gives you an idea of the relative importance of the few largest eigenvectors in representing your image. Include your experimentation in the this notebook so I can see the various different sets you used and the resulting image quality.

Your work for questions 1 and 2 should appear below¶

Answer for part 1¶

In [ ]:
from google.colab import files
uploaded1 = files.upload()
uploaded2 = files.upload()
uploaded3 = files.upload()
uploadedfinale = files.upload()
Upload widget is only available when the cell has been executed in the current browser session. Please rerun this cell to enable.
Saving S.V.Dpt1.jpg to S.V.Dpt1 (3).jpg
Upload widget is only available when the cell has been executed in the current browser session. Please rerun this cell to enable.
Saving S.V.Dpt2.jpg to S.V.Dpt2 (2).jpg
Upload widget is only available when the cell has been executed in the current browser session. Please rerun this cell to enable.
Saving S.V.Dpt3patched.jpg to S.V.Dpt3patched.jpg
Upload widget is only available when the cell has been executed in the current browser session. Please rerun this cell to enable.
Saving S.V.Dfinale.jpg to S.V.Dfinale (2).jpg
In [ ]:
from PIL import Image

part1 = Image.open("S.V.Dpt1.jpg").rotate(-90, expand=True)
part1 = part1.resize((600, 800))
display(part1)

part2 = Image.open("S.V.Dpt2.jpg").rotate(-90, expand=True)
part2 = part2.resize((600, 800))
display(part2)

part3 = Image.open("S.V.Dpt3patched.jpg").rotate(-90, expand=True)
part3 = part3.resize((600, 800))
display(part3)

finale = Image.open("S.V.Dfinale.jpg")
finale = finale.resize((1000, 350))
display(finale)
No description has been provided for this image
No description has been provided for this image
No description has been provided for this image
No description has been provided for this image
In [ ]:
from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
import math
In [ ]:
from google.colab import files
uploaded = files.upload()
Upload widget is only available when the cell has been executed in the current browser session. Please rerun this cell to enable.
Saving dog.jpg to dog.jpg
In [ ]:
dog=Image.open("dog.jpg")
display(dog)
No description has been provided for this image
In [ ]:
dog=dog.convert('L') #convert to black and white
dog=dog.resize((600,400)) #resize to 600x400 pixels
display(dog)
No description has been provided for this image
In [ ]:
dogarray=np.asarray(dog)

dogarray
Out[ ]:
array([[ 54,  54,  53, ...,  81,  81,  82],
       [ 54,  54,  54, ...,  81,  82,  81],
       [ 52,  53,  54, ...,  80,  81,  81],
       ...,
       [134, 134, 132, ...,  83,  85,  87],
       [132, 134, 132, ...,  86,  85,  85],
       [131, 130, 131, ...,  88,  86,  86]], dtype=uint8)
In [ ]:
(u,s,v)=np.linalg.svd(dogarray)

Sigma = np.zeros((600, 400))
Sigma[0:400, 0:400] = np.diag(s)

# Rank 100 approximation of the matrix
approxdogarray = u[0:400, 0:100] @ Sigma[0:100, 0:100] @ v[0:100, 0:600]
approxdogarray=approxdogarray.astype(np.uint8)

approxdog=Image.fromarray(approxdogarray)
approxdog
Out[ ]:
No description has been provided for this image

Answer for part 2¶

In [ ]:
from google.colab import files
uploaded = files.upload()
Upload widget is only available when the cell has been executed in the current browser session. Please rerun this cell to enable.
Saving MATH352SVD.jpg to MATH352SVD.jpg
In [ ]:
from PIL import Image
import numpy as np

#before
print("Original Image")


# Open and preprocess the image
image = Image.open("MATH352SVD.jpg")
link = Image.open("MATH352SVD.jpg")
display(link)
image = image.convert('L')  # convert to black and white
image = image.resize((600, 400))  # resize to 600x400 pixels

# Display the original image in black and white
print("Image scaled and monochromed")
display(image)


#spacer
print("")

# Convert the image to a numpy array
image_array = np.asarray(image)

print(f"Image array = \n{image_array} ")

#spacer
print("")

# Perform Singular Value Decomposition
u, s, v = np.linalg.svd(image_array)

# Construct the diagonal matrix Sigma
Sigma = np.zeros((600, 400))
Sigma[0:400, 0:400] = np.diag(s)

# Rank k approximation of the matrix
def rank_k_approximation(k):
    approx_image_array = u[:, :k] @ Sigma[:k, :k] @ v[:k, :]
    approx_image_array = approx_image_array.astype(np.uint8)
    return Image.fromarray(approx_image_array)

# Calculate memory sizes
original_memory = image_array.size  # Number of entries in the original array
svd_memory = u.size + Sigma.size + v.size  # Number of entries in U, Sigma, and V matrices
approx_memory = {}

# Calculate memory sizes for each approximation and display the approximated images
for k in [10, 50, 100, 200]:
    # Calculate memory size for the current approximation
    approx_memory[k] = (u[:, :k].size + Sigma[:k, :k].size + v[:k, :].size)

    # Display the memory size above the current approximation
    print(f"Memory size for rank {k} approximation:", approx_memory[k])

    # Display the current approximation
    display(rank_k_approximation(k))

# Print memory sizes and the value of k that balances image quality and space saving
print("\nOriginal image memory:", original_memory)
print("SVD memory:", svd_memory)
print("Size of storage needed for rank k SVD approximation:")
for k, memory in approx_memory.items():
    print(f"Rank {k} approximation memory:", memory)
Original Image
No description has been provided for this image
Image scaled and monochromed
No description has been provided for this image
Image array = 
[[ 65  65  65 ...  68  67  67]
 [ 65  65  65 ...  67  67  67]
 [ 64  64  64 ...  67  67  67]
 ...
 [101 101 102 ...  80  80  80]
 [101 101 101 ...  79  79  79]
 [101 101 101 ...  80  79  79]] 

Memory size for rank 10 approximation: 10100
No description has been provided for this image
Memory size for rank 50 approximation: 52500
No description has been provided for this image
Memory size for rank 100 approximation: 110000
No description has been provided for this image
Memory size for rank 200 approximation: 240000
No description has been provided for this image
Original image memory: 240000
SVD memory: 760000
Size of storage needed for rank k SVD approximation:
Rank 10 approximation memory: 10100
Rank 50 approximation memory: 52500
Rank 100 approximation memory: 110000
Rank 200 approximation memory: 240000

Enter your answer to question 3 in this cell¶

Size of your original file: 240000

Size of storage of full SVD: 760000

Value of k you found that seemed a good balance of image quality and space saving: k = 100

Size of storage needed for your rank k SVD approximation: 110000

Add your code for question 4 in the cells below¶

In [ ]:
# Rank k approximation of the matrix with different subsets
def rank_k_approximation_experiments(k):
    # Skip the first 3 columns of U, rows of V, and diagonal values of Sigma
    approx_image_array = u[:, 3:k+3] @ Sigma[3:k+3, 3:k+3] @ v[3:k+3, :]
    approx_image_array = approx_image_array.astype(np.uint8)
    return Image.fromarray(approx_image_array)

# Experimenting with different sets of rows and columns, we'll use the same k values for consistency
for k in [10, 50, 100, 200]:
    # Display the current approximation
    print(f"rank {k} aprroximation")
    display(rank_k_approximation_experiments(k))


#Holy crap nightmare fuel
rank 10 aprroximation
No description has been provided for this image
rank 50 aprroximation
No description has been provided for this image
rank 100 aprroximation
No description has been provided for this image
rank 200 aprroximation
No description has been provided for this image

yeahhhhh it looks way worse when you lose that data. The finer background details are completely obliterated and a lot of the facial details also get lost. You can see that the silloette is still somewhat recognizable, but this really shows how important those first 3 rows and columns of data are.

In [ ]: